package com.hc.programming.hash;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 给定两个数组 nums1 和 nums2 ，返回 它们的 交集。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
 * <p>
 * 示例 1：
 * 输入：nums1 = [1,2,2,1], nums2 = [2,2]
 * 输出：[2]
 * 示例 2：
 * 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 * 输出：[9,4]
 * 解释：[4,9] 也是可通过的
 * <p>
 * 提示：
 * 1 <= nums1.length, nums2.length <= 1000
 * 0 <= nums1[i], nums2[i] <= 1000
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/10/23 21:35
 */
public class 两个数组的交集 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(intersection( new int[]{1, 2, 2, 1}, new int[]{2, 2})));
        System.out.println(Arrays.toString(intersection( new int[]{4, 9, 5}, new int[]{9, 4, 9, 8, 4})));
    }

    public static int[] intersection(int[] nums1, int[] nums2) {
//        return set(nums1, nums2);
//        return array(nums1, nums2);
        return array2(nums1, nums2);
    }

    private static int[] array2(int[] nums1, int[] nums2) {
        int[] count1 = new int[1001]; // 1-nums1存在；2-两边都存在
        int[] count2 = new int[1001]; // 记录有效元素
        for (int num : nums1) count1[num] = 1;
        int i = 0;
        for (int num : nums2) {
            if (count1[num] == 1) {
                count1[num] = 2;
                count2[i++] = num;
            }
        }
        return Arrays.copyOf(count2, i);
    }

    private static int[] array(int[] nums1, int[] nums2) {
        int[] count1 = new int[1001];
        int[] count2 = new int[1001];
        for (int num : nums1) count1[num]++;
        for (int num : nums2) count2[num]++;
        int[] res = new int[Math.min(nums1.length, nums2.length)];
        int i = 0;
        for (int j = 0; j < 1001; j++) {
            if (count1[j] > 0 && count2[j] > 0) {
                res[i++] = j;
            }
        }
        return Arrays.copyOf(res, i);
    }

    private static int[] set(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums1) set.add(num);
        Set<Integer> result = new HashSet<>();
        for (int num : nums2) {
            if (set.contains(num)) {
                result.add(num);
            }
        }
        int[] res = new int[result.size()];
        int i = 0;
        for (int num : result) {
            res[i++] = num;
        }
        return res;
    }
}
